#include <time.h>
#include <vector>
#include <stdlib.h>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <functional>

using namespace std;

// 215. 数组中的第K个最大元素
class Solution1
{
private:
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }

    int qsort(vector<int>& nums, int left, int right, int k)
    {
        if(left == right) return nums[left];

        int key = getRandom(nums, left, right);
        int l = left - 1, i = left, r = right + 1;
        while(i < r)
        {
            if(nums[i] < key) swap(nums[++l], nums[i++]);
            else if(nums[i] == key) ++i;
            else swap(nums[--r], nums[i]);
        }

        int c = right - r + 1, b = r - l - 1;
        if(c >= k) return qsort(nums, r, right, k);
        else if(b + c >= k) return key;
        else return qsort(nums, left, l, k - b - c);
    }

public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(nullptr));
        return qsort(nums, 0, nums.size() - 1, k);
    }
};

// 347. 前 K 个高频元素
class Solution2
{
private:
    struct cmp
    {
        bool operator()(pair<int, int>& a, pair<int, int>& b)
        {
            return a.second > b.second;
        }
    };

public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        unordered_map<int, int> m;
        for(int x : nums) ++m[x];

        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
        for(auto& kv : m)
        {
            if(q.size() == k)
            {
                if(q.top().second < kv.second)
                {
                    q.pop();
                    q.emplace(kv);
                }
            }
            else
                q.emplace(kv);
        }

        vector<int> ret;
        while(!q.empty())
        {
            ret.push_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

// 121. 买卖股票的最佳时机
class Solution3
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int ret = 0, n = prices.size(), minPrice = INT_MAX;
        for(int i = 0; i < n; ++i)
        {
            minPrice = min(minPrice, prices[i]);
            ret = max(ret, prices[i] - minPrice);
        }
        return ret; 
    }
};

// 45. 跳跃游戏 II
class Solution3
{
public:
    int jump(vector<int>& nums) 
    {
        int cur = 0, next = 0, ret = 0;
        for(int i = 0; i < nums.size() - 1; ++i)
        {
            next = max(i + nums[i], next);
            if(i == cur)
            {
                ++ret;
                cur = next;
            }
        }
        return ret;
    }
};

// 84. 柱状图中最大的矩形
class Solution4
{
public:
    int largestRectangleArea(vector<int>& heights) 
    {
        int n = heights.size();
        // 利用单调栈(栈底->栈顶:小->大)找出左右两边第一个比heights[i]小的数字
        vector<int> left(n), right(n, n);

        stack<int> st;
        for(int i = 0; i < n; ++i)
        {
            while(!st.empty() && heights[st.top()] >= heights[i]) 
            {
                right[st.top()] = i;
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }


        int ret = 0;
        for(int i = 0; i < n; ++i)
        {
            ret = max(ret, (right[i] - left[i] - 1) * heights[i]);
        }
        return ret;
    }
};

// 212. 单词搜索 II
struct TrieNode
{
    string word; // 字符串的最后一个字符的节点存数据
    vector<TrieNode*> children;

    TrieNode()
        : word("")
        , children(26)
    {}
};

void insert(TrieNode* root, const string& word)
{
    TrieNode* node = root;
    for(char ch : word)
    {
        ch -= 'a';
        if(node->children[ch] == nullptr)
        {
            node->children[ch] = new TrieNode();
        }
        node = node->children[ch];
    }
    node->word = word; // 结尾字符的节保存数据
}

class Solution5
{
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) 
    {
        const int dx[4] = {0, 0, 1, -1};
        const int dy[4] = {1, -1, 0, 0};

        set<string> s;
        int m = board.size(), n = board[0].size();
        TrieNode* root = new TrieNode();
        for(auto& word : words) insert(root, word);

        function<bool(int i, int j, TrieNode*)> dfs = [&](int i, int j, TrieNode* node)
        {
            char ch = board[i][j];
            if(!node->children[ch - 'a']) return false;

            node = node->children[ch - 'a'];
            if(node->word.size() > 0) s.insert(node->word);

            board[i][j] = '#'; // 标记该字符已经访问过了
            for(int k = 0; k < 4; ++k)
            {
                int x = i + dx[k], y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#')
                {
                    dfs(x, y, node);
                }
            }
            board[i][j] = ch;

            return true;
        };

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                dfs(i, j, root);
            }
        }

        vector<string> ret;
        for(auto& word : s)
        {
            ret.emplace_back(word);
        }
        return ret;
    }
};

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 105. 从前序与中序遍历序列构造二叉树
class Solution6
{
private:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int& pre, int begin, int end)
    {
        if(begin > end) return nullptr;

        TreeNode* root = new TreeNode(preorder[pre]);
        int i = begin;
        while(i <= end)
        {
            if(inorder[i] == root->val) break;
            else ++i;
        }

        ++pre;
        root->left = buildTree(preorder, inorder, pre, begin, i - 1);
        root->right = buildTree(preorder, inorder, pre, i + 1, end);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int pre = 0;
        return buildTree(preorder, inorder, pre, 0, inorder.size() - 1);
    }
};

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 148. 排序链表
class Solution7
{
private:
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        ListNode* newHead = new ListNode(), *tail = newHead;
        ListNode* cur1 = head1, *cur2 = head2;

        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }

        tail->next = cur1 ? cur1 : cur2;

        cur1 = newHead->next;
        delete newHead;
        return cur1;
    }

    ListNode* sortList(ListNode* head, ListNode* tail)
    {
        if(head == nullptr) return nullptr;
        if(head->next == tail)
        {
            head->next = nullptr;
            return head;
        }

        ListNode* slow = head, *fast = head;
        while(fast != tail && fast->next != tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return merge(sortList(head, slow), sortList(slow, tail));
    }

public:
    ListNode* sortList(ListNode* head) 
    {
        return sortList(head, nullptr);
    }
};

// 23. 合并 K 个升序链表
class Solution8
{
private:
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 创建一个小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        // 让所有的头结点进入小根堆
        for(auto l : lists)
        {
            if(l) heap.push(l);
        }

        // 合并 k 个有序链表
        ListNode* newHead = new ListNode;
        ListNode* tail = newHead;
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            tail->next = t;
            tail = t;
            if(t->next) heap.push(t->next);
        }

        tail = newHead->next;
        delete newHead;
        return tail;
    }
};

// 295. 数据流的中位数
class MedianFinder 
{
private:
    priority_queue<int, vector<int>, less<int>> left;
    priority_queue<int, vector<int>, greater<int>> right;

public:
    MedianFinder() 
    {}
    
    void addNum(int num) 
    {
        if(left.size() == right.size())
        {
            if(left.empty() || num <= left.top())
                left.push(num);
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else
        {
            if(right.empty() && num >= left.top())
                right.push(num);
            else
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
        }
    }
    
    double findMedian() 
    {
        if(left.size() == right.size())
            return (left.top() + right.top()) / 2.0;
        return left.top();
    }
};

// 4. 寻找两个正序数组的中位数
class Solution9
{
private:
        int getKth(vector<int>& arr1, int begin1, int end1, vector<int>& arr2, int begin2, int end2, int k)
        {
            int len1 = end1 - begin1 + 1, len2 = end2 - begin2 + 1;
            if(len1 > len2) return getKth(arr2, begin2, end2, arr1, begin1, end1, k);
            if(len1 == 0) return arr2[begin2 + k - 1];

            if(k == 1) return min(arr1[begin1], arr2[begin2]);

            int i = begin1 + min(len1, k / 2) - 1;
            int j = begin2 + min(len2, k / 2) - 1;

            if(arr1[i] > arr2[j])
                return getKth(arr1, begin1, end1, arr2, j + 1, end2, k - (j - begin2 + 1));
            else
                return getKth(arr1, i + 1, end1, arr2, begin2, end2, k - (i - begin1 + 1));
        }

public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        int m = nums1.size(), n = nums2.size();
        int left = (m + n + 1) / 2, right = (m + n + 2) / 2;



        return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, left) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, right)) / 2.0;
    }
};